<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>

<body>
    <script>
        // 给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。

        var nums = [-1, 0, 1, 2, -1, -4]
        // 暴力破解

        // 排序 哈希表 主要难点是去重 
        function fn(nums) {
            var len = nums.length;
            // 排序
            nums.sort((a, b) => {
                return a - b
            })
            // 记入哈希表
            var map = new Map();
            for (var i = 0; i < nums.length; i++) {
                map.set(nums[i], i) 
            }
            console.log(map);
            var result = [];
            for (var first = 0; first < len - 2; first++) {
                if (nums[first] > 0) { break; }
                if (first > 0 && nums[first] == nums[first - 1]) {
                    continue
                }
                var target = -nums[first];
                for (var second = first + 1; second < len; second++) {
                    if (second > first + 1 && nums[second] == nums[second - 1]) {
                        continue
                    }
                    if (map.has(target - nums[second])) {
                        var third = map.get(target - nums[second]);

                        if (third > second) {
                            result.push([nums[first], nums[second], nums[third]])
                        } else {
                            break;
                        }
                    }
                }
            }
            return result
        }
        console.log(fn(nums));




        // 排序 双指针 难点 去重
        function threeNum(nums) {
            nums.sort((a, b) => {
                return a - b
            })
            var res = [];
            for (var i = 0; i < nums.length - 2; i++) {
                if (nums[i] > 0) {
                    break
                }
                // 去掉第一个数字的重复情况
                if (i > 0 && nums[i] == nums[i - 1]) {
                    continue
                }
                var target = -nums[i];
                for (var x = i + 1, y = nums.length - 1; x < y;) {
                    if (nums[x] + nums[y] == target) {
                        res.push([nums[i], nums[x], nums[y]]);
                        // 判断重复的情况
                        // while (x < y && nums[x] == nums[++x]) { }
                        // while (x < y && nums[y] == nums[--y]) { }
                        while (x < y && nums[x] == nums[x + 1]) {
                            x++
                        }
                        while (x < y && nums[y] == nums[y - 1]) {
                            y--
                        }
                        x++;
                        y--;
                    } else if (nums[x] + nums[y] > target) {
                        // while (x < y && nums[y] == nums[--y]) { }
                        while (x < y && nums[y] == nums[y - 1]) {
                            y--
                        }
                        y--
                    } else {
                        // while (x < y && nums[x] == nums[++x]) { }
                        while (x < y && nums[x] == nums[x + 1]) {
                            x++;
                        }
                        x++
                    }
                }

            }
            return res;
        }



        console.log(foo(nums));
    </script>
</body>

</html>